/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/house-robber-ii
   @Language: C++
   @Datetime: 20-01-07 18:49
   */

class Solution {
	int rob(vector<int>& nums, int begin, int end) {
		int robbed=0, unrobbed=0;
		for(int i=begin; i<end; ++i){
			int r = unrobbed+nums[i];
			int u = max(robbed, unrobbed);
			robbed = r;
			unrobbed = u;
		}
		return max(robbed, unrobbed);
	}
public:
	int rob(vector<int>& nums) {
		if (nums.size()==1) return nums[0];
		return max(rob(nums, 0, nums.size()-1), rob(nums, 1, nums.size()));
	}
};
